Search Results

Documents authored by Lombardy, Sylvain

Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2023
LIPIcs, Volume 272, MFCS 2023, Complete Volume

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
LIPIcs, Volume 272, MFCS 2023, Complete Volume
Cite as

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 1-1302, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{leroux_et_al:LIPIcs.MFCS.2023,
  title =	{{LIPIcs, Volume 272, MFCS 2023, Complete Volume}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{1--1302},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023},
  URN =		{urn:nbn:de:0030-drops-185332},
  doi =		{10.4230/LIPIcs.MFCS.2023},
  annote =	{Keywords: LIPIcs, Volume 272, MFCS 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Jérôme Leroux, Sylvain Lombardy, and David Peleg

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leroux_et_al:LIPIcs.MFCS.2023.0,
  author =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.0},
  URN =		{urn:nbn:de:0030-drops-185349},
  doi =		{10.4230/LIPIcs.MFCS.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.32
Unambiguous Separators for Tropical Tree Automata

Authors: Thomas Colcombet and Sylvain Lombardy

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this paper we show that given a max-plus automaton (over trees, and with real weights) computing a function f and a min-plus automaton (similar) computing a function g such that f ⩽ g, there exists effectively an unambiguous tropical automaton computing h such that f ⩽ h ⩽ g. This generalizes a result of Lombardy and Mairesse of 2006 stating that series which are both max-plus and min-plus rational are unambiguous. This generalization goes in two directions: trees are considered instead of words, and separation is established instead of characterization (separation implies characterization). The techniques in the two proofs are very different.
Cite as

Thomas Colcombet and Sylvain Lombardy. Unambiguous Separators for Tropical Tree Automata. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{colcombet_et_al:LIPIcs.STACS.2020.32,
  author =	{Colcombet, Thomas and Lombardy, Sylvain},
  title =	{{Unambiguous Separators for Tropical Tree Automata}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.32},
  URN =		{urn:nbn:de:0030-drops-118933},
  doi =		{10.4230/LIPIcs.STACS.2020.32},
  annote =	{Keywords: Tree automata, Tropical semiring, Separation, Unambiguity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.6
On Hadamard Series and Rotating Q-Automata

Authors: Louis-Marie Dando and Sylvain Lombardy

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper, we study rotating Q-automata, which are (memoryless) automata with weights in Q, that can read the input tape from left to right several times. We show that the series realized by valid rotating Q-automata are Q-Hadamard series (which are the closure of Q-rational series by pointwise inverse), and that every Q-Hadamard series can be realized by such an automaton. We prove that, although validity of rotating Q-automata is undecidable, the equivalence problem is decidable on rotating Q-automata. Finally, we prove that every valid two-way Q-automaton admits an equivalent rotating Q-automaton. The conversion, which is effective, implies the decidability of equivalence of two-way Q-automata.
Cite as

Louis-Marie Dando and Sylvain Lombardy. On Hadamard Series and Rotating Q-Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dando_et_al:LIPIcs.MFCS.2018.6,
  author =	{Dando, Louis-Marie and Lombardy, Sylvain},
  title =	{{On Hadamard Series and Rotating Q-Automata}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.6},
  URN =		{urn:nbn:de:0030-drops-95881},
  doi =		{10.4230/LIPIcs.MFCS.2018.6},
  annote =	{Keywords: Rational series, Hadamard operations, Rotating automata, Two-way automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1850
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

Authors: Daniel Kirsten and Sylvain Lombardy

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.
Cite as

Daniel Kirsten and Sylvain Lombardy. Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 589-600, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kirsten_et_al:LIPIcs.STACS.2009.1850,
  author =	{Kirsten, Daniel and Lombardy, Sylvain},
  title =	{{Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{589--600},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1850},
  URN =		{urn:nbn:de:0030-drops-18509},
  doi =		{10.4230/LIPIcs.STACS.2009.1850},
  annote =	{Keywords: Min-plus automata, Determinization, Finite semigroups}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact